# The Sugiyama variation of the Euclidean division algorithm

from PyM import *

# def sugiyama(r0,r1,t):
#     v0 = 0; v1 = 1
#     while t <= degree(r1):
#         [q,r] = quo_rem(r0,r1)
#         v = v0-q*v1
#         r0 = r1; r1 = r; v0 = v1; v1 = v
#     return (v1,r1)

# Example #
[P,z] = polynomial_ring(ZZ(),'z')  # ,'Z[z]' 
r = 4; S = z**3+z; t = 2
(L,E) = sugiyama(z**r,S,t)

show(L)
show(E)
show((L*S-E)%z**r)  # check divisibility by z**r